package com.melo;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc 字符串匹配: KMP算法<a href="https://www.cnblogs.com/zzuuoo666/p/9028287.html">KMP算法详解</a>
 * @date 2025-04-29
 */
public class KmpMatch {

    /**
     * 字符串KMP算法匹配
     *
     * @param source 源字符串: 被匹配的字符串
     * @param dest   目标字符串: 匹配的字符串
     * @return 匹配到的字符串的位置, 没有匹配到返回-1
     */
    public static int kmpMatch(String source, String dest) {
        int[] kmpPartialMatchTable = calKmpPartialMatchTable(dest);

        for (int i = 0, j = 0; i < source.length(); i++) {
            // KMP算法核心所在
            while (j > 0 && source.charAt(i) != dest.charAt(j)) {
                j = kmpPartialMatchTable[j - 1];
            }

            if (source.charAt(i) == dest.charAt(j)) {
                j++;
            }
            if (j == dest.length()) {
                return i - j + 1;
            }
        }

        return -1;
    }

    /**
     * 计算要匹配字符串的部分匹配表
     *
     * @param destStr 要匹配的字符串
     * @return 部分匹配表
     */
    public static int[] calKmpPartialMatchTable(String destStr) {
        int[] kmpPartialMatchTable = new int[destStr.length()];

        // 如果字符串是长度为1, 部分匹配值就是0
        kmpPartialMatchTable[0] = 0;
        for (int i = 1, j = 0; i < destStr.length(); i++) {
            while (j > 0 && destStr.charAt(i) != destStr.charAt(j)) {
                j = kmpPartialMatchTable[j - 1];
            }

            if (destStr.charAt(i) == destStr.charAt(j)) {
                j++;
            }
            kmpPartialMatchTable[i] = j;
        }

        return kmpPartialMatchTable;
    }
}
